/*-------------------------------------------------------------------------
 *
 * gistproc.c
 *	  GiST支持程序，处理二维对象（盒子、多边形、圆形、点）。
 *
 * 这提供了R树行为，采用Guttman的多项式时间分裂算法。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	src/backend/access/gist/gistproc.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <math.h>

#include "access/gist.h"
#include "access/stratnum.h"
#include "utils/builtins.h"
#include "utils/float.h"
#include "utils/geo_decls.h"
#include "utils/sortsupport.h"


static bool fc_gist_box_leaf_consistent(BOX *fc_key, BOX *fc_query,
									 StrategyNumber fc_strategy);
static bool fc_rtree_internal_consistent(BOX *fc_key, BOX *fc_query,
									  StrategyNumber fc_strategy);

static uint64 fc_point_zorder_internal(float4 fc_x, float4 fc_y);
static uint64 fc_part_bits32_by2(uint32 fc_x);
static uint32 fc_ieee_float32_to_uint32(float fc_f);
static int	fc_gist_bbox_zorder_cmp(Datum fc_a, Datum fc_b, SortSupport fc_ssup);
static Datum fc_gist_bbox_zorder_abbrev_convert(Datum fc_original, SortSupport fc_ssup);
static bool fc_gist_bbox_zorder_abbrev_abort(int fc_memtupcount, SortSupport fc_ssup);


/* 最小接受的拆分比例 */
#define LIMIT_RATIO 0.3


/**************************************************
 * Box ops
 **************************************************/

/*
 * 计算两个盒子 a 和 b 的并集。结果存储在 *n 中。
 */
static void fc_rt_box_union(BOX *fc_n, const BOX *fc_a, const BOX *fc_b)
{
	fc_n->high.x = float8_max(fc_a->high.x, fc_b->high.x);
	fc_n->high.y = float8_max(fc_a->high.y, fc_b->high.y);
	fc_n->low.x = float8_min(fc_a->low.x, fc_b->low.x);
	fc_n->low.y = float8_min(fc_a->low.y, fc_b->low.y);
}

/*
 * 进行惩罚计算时 BOX 的大小。
 * 结果可以是 +Infinity，但不能是 NaN。
 */
static float8 fc_size_box(const BOX *fc_box)
{
	/*
	 * 检查零宽度情况。请注意，我们将零-
	 * 乘以无限的盒子的大小定义为零。以某种方式特殊处理这一点很重要，
	 * 因为天真的将无限乘以零会产生 NaN。
	 *
	 * 小于的情况不应该发生，但如果发生了，则返回“零”。
	 */
	if (float8_le(fc_box->high.x, fc_box->low.x) ||
		float8_le(fc_box->high.y, fc_box->low.y))
		return 0.0;

	/*
	 * 我们将 NaN 视为比 +Infinity 更大，因此任何涉及 NaN
	 * 和非 NaN 的距离都是无限的。请注意先前的检查消除了
	 * 低字段是 NaN 的可能性。
	 */
	if (isnan(fc_box->high.x) || isnan(fc_box->high.y))
		return get_float8_infinity();
	return float8_mul(float8_mi(fc_box->high.x, fc_box->low.x),
					  float8_mi(fc_box->high.y, fc_box->low.y));
}

/*
 * 返回两个盒子的并集比
 * 原始 BOX 的面积大多少。结果可以是 +Infinity，但不能是 NaN。
 */
static float8 fc_box_penalty(const BOX *fc_original, const BOX *fc_new)
{
	BOX			fc_unionbox;

	fc_rt_box_union(&fc_unionbox, fc_original, fc_new);
	return float8_mi(fc_size_box(&fc_unionbox), fc_size_box(fc_original));
}

/*
 * 盒子的 GiST 一致性方法
 *
 * 如果所有数据项 x 在条目之下，
 * 则谓词 x op 查询必须为假，则应返回假，其中 op 是
 * 对应于 pg_amop 表中的策略的操作。
 */
Datum gist_box_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	BOX		   *fc_query = PG_GETARG_BOX_P(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);

	/* 由此函数服务的所有案例都是精确的 */
	*fc_recheck = false;

	if (DatumGetBoxP(fc_entry->key) == NULL || fc_query == NULL)
		PG_RETURN_BOOL(false);

	/*
	 * 如果条目不是叶子，使用 rtree_internal_consistent，否则使用
	 * gist_box_leaf_consistent
	 */
	if (GIST_LEAF(fc_entry))
		PG_RETURN_BOOL(fc_gist_box_leaf_consistent(DatumGetBoxP(fc_entry->key),
												fc_query,
												fc_strategy));
	else
		PG_RETURN_BOOL(fc_rtree_internal_consistent(DatumGetBoxP(fc_entry->key),
												 fc_query,
												 fc_strategy));
}

/*
 * 增加 BOX b 以包括附加内容。
 */
static void fc_adjustBox(BOX *fc_b, const BOX *fc_addon)
{
	if (float8_lt(fc_b->high.x, fc_addon->high.x))
		fc_b->high.x = fc_addon->high.x;
	if (float8_gt(fc_b->low.x, fc_addon->low.x))
		fc_b->low.x = fc_addon->low.x;
	if (float8_lt(fc_b->high.y, fc_addon->high.y))
		fc_b->high.y = fc_addon->high.y;
	if (float8_gt(fc_b->low.y, fc_addon->low.y))
		fc_b->low.y = fc_addon->low.y;
}

/*
 * 盒子的 GiST 并集方法
 *
 * 返回包含 entryvec 中所有条目的最小边界盒
 */
Datum gist_box_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	int		   *fc_sizep = (int *) PG_GETARG_POINTER(1);
	int			fc_numranges,
				fc_i;
	BOX		   *fc_cur,
			   *fc_pageunion;

	fc_numranges = fc_entryvec->n;
	fc_pageunion = (BOX *) palloc(sizeof(BOX));
	fc_cur = DatumGetBoxP(fc_entryvec->vector[0].key);
	memcpy((void *) fc_pageunion, (void *) fc_cur, sizeof(BOX));

	for (fc_i = 1; fc_i < fc_numranges; fc_i++)
	{
		fc_cur = DatumGetBoxP(fc_entryvec->vector[fc_i].key);
		fc_adjustBox(fc_pageunion, fc_cur);
	}
	*fc_sizep = sizeof(BOX);

	PG_RETURN_POINTER(fc_pageunion);
}

/*
 * 我们在 GiST 索引中将盒子存储为盒子，因此不需要
 * 压缩、解压或获取函数。
 */

/*
 * 盒子的 GiST 惩罚方法（也用于点）
 *
 * 正如 R-tree 论文中所述，我们使用面积变化作为我们的惩罚度量
 */
Datum gist_box_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_result = (float *) PG_GETARG_POINTER(2);
	BOX		   *fc_origbox = DatumGetBoxP(fc_origentry->key);
	BOX		   *fc_newbox = DatumGetBoxP(fc_newentry->key);

	*fc_result = (float) fc_box_penalty(fc_origbox, fc_newbox);
	PG_RETURN_POINTER(fc_result);
}

/*
 * 平凡的拆分：一半条目将放置在一页
 * 另一半 - 放到另一页
 */
static void fc_fallbackSplit(GistEntryVector *fc_entryvec, GIST_SPLITVEC *fc_v)
{
	OffsetNumber fc_i,
				fc_maxoff;
	BOX		   *fc_unionL = NULL,
			   *fc_unionR = NULL;
	int			fc_nbytes;

	fc_maxoff = fc_entryvec->n - 1;

	fc_nbytes = (fc_maxoff + 2) * sizeof(OffsetNumber);
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_nleft = fc_v->spl_nright = 0;

	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		BOX		   *fc_cur = DatumGetBoxP(fc_entryvec->vector[fc_i].key);

		if (fc_i <= (fc_maxoff - FirstOffsetNumber + 1) / 2)
		{
			fc_v->spl_left[fc_v->spl_nleft] = fc_i;
			if (fc_unionL == NULL)
			{
				fc_unionL = (BOX *) palloc(sizeof(BOX));
				*fc_unionL = *fc_cur;
			}
			else
				fc_adjustBox(fc_unionL, fc_cur);

			fc_v->spl_nleft++;
		}
		else
		{
			fc_v->spl_right[fc_v->spl_nright] = fc_i;
			if (fc_unionR == NULL)
			{
				fc_unionR = (BOX *) palloc(sizeof(BOX));
				*fc_unionR = *fc_cur;
			}
			else
				fc_adjustBox(fc_unionR, fc_cur);

			fc_v->spl_nright++;
		}
	}

	fc_v->spl_ldatum = BoxPGetDatum(fc_unionL);
	fc_v->spl_rdatum = BoxPGetDatum(fc_unionR);
}

/*
 * 表示可以放置到任一组的条目的信息
 * 而不影响选定轴上的重叠（“共同条目”）。
 */
typedef struct
{
	/* 初始数组中条目的索引 */
	int			index;
	/* 插入条目到不同组之间的惩罚差值 */
	float8		delta;
} CommonEntry;

/*
 * g_box_consider_split 的上下文。包含有关当前
 * 选定拆分和一些一般信息的信息。
 */
typedef struct
{
	int			entriesCount;	/* 被拆分的条目总数 */
	BOX			boundingBox;	/* 所有条目的最小边界盒 */

	/* 目前选定拆分的信息如下 */

	bool		first;			/* 如果尚未选择拆分则为真 */

	float8		leftUpper;		/* 左间隔的上限 */
	float8		rightLower;		/* 右间隔的下限 */

	float4		ratio;
	float4		overlap;
	int			dim;			/* 此拆分的轴 */
	float8		range;			/* 投影到所选轴的通用 MBR 的宽度 */
} ConsiderSplitContext;

/*
 * 区间表示盒子到轴的投影。
 */
typedef struct
{
	float8		lower,
				upper;
} SplitInterval;

/*
 * 根据区间的下限进行的区间比较函数；
 */
static int fc_interval_cmp_lower(const void *fc_i1, const void *fc_i2)
{
	float8		fc_lower1 = ((const SplitInterval *) fc_i1)->lower,
				fc_lower2 = ((const SplitInterval *) fc_i2)->lower;

	return float8_cmp_internal(fc_lower1, fc_lower2);
}

/*
 * 按区间的上界进行区间比较函数;
 */
static int fc_interval_cmp_upper(const void *fc_i1, const void *fc_i2)
{
	float8		fc_upper1 = ((const SplitInterval *) fc_i1)->upper,
				fc_upper2 = ((const SplitInterval *) fc_i2)->upper;

	return float8_cmp_internal(fc_upper1, fc_upper2);
}

/*
 * 用零替换负值（或NaN）。
 */
static inline float
fc_non_negative(float fc_val)
{
	if (fc_val >= 0.0f)
		return fc_val;
	else
		return 0.0f;
}

/*
 * 考虑用更好的分割替换当前选择的分割。
 */
static inline void fc_g_box_consider_split(ConsiderSplitContext *fc_context, int fc_dimNum,
					 float8 fc_rightLower, int fc_minLeftCount,
					 float8 fc_leftUpper, int fc_maxLeftCount)
{
	int			fc_leftCount,
				fc_rightCount;
	float4		fc_ratio,
				fc_overlap;
	float8		fc_range;

	/*
	 * 计算条目分布比率，假设公共条目的分布最为均匀。
	 */
	if (fc_minLeftCount >= (fc_context->entriesCount + 1) / 2)
	{
		fc_leftCount = fc_minLeftCount;
	}
	else
	{
		if (fc_maxLeftCount <= fc_context->entriesCount / 2)
			fc_leftCount = fc_maxLeftCount;
		else
			fc_leftCount = fc_context->entriesCount / 2;
	}
	fc_rightCount = fc_context->entriesCount - fc_leftCount;

	/*
	 * 分割的比率 - 较小组的大小与总条目数的商。
	 */
	fc_ratio = float4_div(Min(fc_leftCount, fc_rightCount), fc_context->entriesCount);

	if (fc_ratio > LIMIT_RATIO)
	{
		bool		fc_selectthis = false;

		/*
		 * 比率是可以接受的，因此将当前分割与之前选择的分割进行比较。在一个维度的分割中，我们寻找最小的重叠（允许负值）和最小的比率（在相同的重叠之间）。如果找到较少的重叠（非负）或在相同重叠下的较小范围，则切换维度。
		 */
		if (fc_dimNum == 0)
			fc_range = float8_mi(fc_context->boundingBox.high.x,
							  fc_context->boundingBox.low.x);
		else
			fc_range = float8_mi(fc_context->boundingBox.high.y,
							  fc_context->boundingBox.low.y);

		fc_overlap = float8_div(float8_mi(fc_leftUpper, fc_rightLower), fc_range);

		/* 如果没有之前的选择，选择这个 */
		if (fc_context->first)
			fc_selectthis = true;
		else if (fc_context->dim == fc_dimNum)
		{
			/*
			 * 在相同维度内，如果新分割有更小的重叠，或相同的重叠但更好的比率，则选择新分割。
			 */
			if (fc_overlap < fc_context->overlap ||
				(fc_overlap == fc_context->overlap && fc_ratio > fc_context->ratio))
				fc_selectthis = true;
		}
		else
		{
			/*
			 * 在不同维度之间，如果新分割有更小的*非负*重叠，或相同的*非负*重叠但更大的范围，则选择新分割。这个条件与文章中描述的有所不同。在叶MBR不彼此重叠的数据集中，非重叠的分割（即重叠为零的分割）是常见的。在这种情况下，分割往往沿着一个维度进行，因为最远的非重叠分割（即负重叠最低的）似乎与之前的分割位于相同的维度。因此，MBR在另一个维度上看起来非常拉长，这导致搜索性能差。将范围作为第二个分割标准使得MBR更加方形。将*非负*重叠而不是重叠作为第一个分割标准，使得范围标准有机会变得重要，因为在这个标准下，非重叠的分割是等价的。
			 */
			if (fc_non_negative(fc_overlap) < fc_non_negative(fc_context->overlap) ||
				(fc_range > fc_context->range &&
				 fc_non_negative(fc_overlap) <= fc_non_negative(fc_context->overlap)))
				fc_selectthis = true;
		}

		if (fc_selectthis)
		{
			/* 保存有关所选分割的信息 */
			fc_context->first = false;
			fc_context->ratio = fc_ratio;
			fc_context->range = fc_range;
			fc_context->overlap = fc_overlap;
			fc_context->rightLower = fc_rightLower;
			fc_context->leftUpper = fc_leftUpper;
			fc_context->dim = fc_dimNum;
		}
	}
}

/*
 * 通过它们的增量比较公共条目。
 */
static int fc_common_entry_cmp(const void *fc_i1, const void *fc_i2)
{
	float8		fc_delta1 = ((const CommonEntry *) fc_i1)->delta,
				fc_delta2 = ((const CommonEntry *) fc_i2)->delta;

	return float8_cmp_internal(fc_delta1, fc_delta2);
}

/*
 * --------------------------------------------------------------------------
 * 双重排序分割算法。此算法适用于盒子和点。
 *
 * 该算法通过考虑沿每个轴的分割来寻找盒子的分割。
 * 每个条目首先投影为 X 轴上的一个区间，然后考虑将区间分成两个组的不同方式，试图最小化组之间的重叠。然后对 Y 轴重复相同的过程，选择整体最佳的分割。分割的质量由沿该轴的重叠和其他一些标准决定（见 g_box_consider_split）。
 *
 * 之后，所有条目分为三组：
 *
 * 1) 应该放置到左组的条目
 * 2) 应该放置到右组的条目
 * 3) “公共条目”，可以放置到任何组中，而不会影响沿选定轴的重叠。
 *
 * 公共条目通过最小化惩罚分配。
 *
 * 详情见：
 * “一种基于双重排序的新型节点分割算法用于 R 树”，A. Korotkov
 * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
 * --------------------------------------------------------------------------
 */
Datum gist_box_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	OffsetNumber fc_i,
				fc_maxoff;
	ConsiderSplitContext fc_context;
	BOX		   *fc_box,
			   *fc_leftBox,
			   *fc_rightBox;
	int			fc_dim,
				fc_commonEntriesCount;
	SplitInterval *fc_intervalsLower,
			   *fc_intervalsUpper;
	CommonEntry *fc_commonEntries;
	int			fc_nentries;

	memset(&fc_context, 0, sizeof(ConsiderSplitContext));

	fc_maxoff = fc_entryvec->n - 1;
	fc_nentries = fc_context.entriesCount = fc_maxoff - FirstOffsetNumber + 1;

	/* 为轴上的区间分配数组 */
	fc_intervalsLower = (SplitInterval *) palloc(fc_nentries * sizeof(SplitInterval));
	fc_intervalsUpper = (SplitInterval *) palloc(fc_nentries * sizeof(SplitInterval));

	/*
	 * 计算所有条目的整体最小边界框。
	 */
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		fc_box = DatumGetBoxP(fc_entryvec->vector[fc_i].key);
		if (fc_i == FirstOffsetNumber)
			fc_context.boundingBox = *fc_box;
		else
			fc_adjustBox(&fc_context.boundingBox, fc_box);
	}

	/*
	 * 在轴上迭代以搜索最佳分割。
	 */
	fc_context.first = true;		/* 尚未选择任何内容 */
	for (fc_dim = 0; fc_dim < 2; fc_dim++)
	{
		float8		fc_leftUpper,
					fc_rightLower;
		int			fc_i1,
					fc_i2;

		/* 将每个条目投影为选定轴上的一个区间。 */
		for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
		{
			fc_box = DatumGetBoxP(fc_entryvec->vector[fc_i].key);
			if (fc_dim == 0)
			{
				fc_intervalsLower[fc_i - FirstOffsetNumber].lower = fc_box->low.x;
				fc_intervalsLower[fc_i - FirstOffsetNumber].upper = fc_box->high.x;
			}
			else
			{
				fc_intervalsLower[fc_i - FirstOffsetNumber].lower = fc_box->low.y;
				fc_intervalsLower[fc_i - FirstOffsetNumber].upper = fc_box->high.y;
			}
		}

		/*
		 * 创建两个区间数组：一个按下限排序，另一个按上限排序。
		 */
		memcpy(fc_intervalsUpper, fc_intervalsLower,
			   sizeof(SplitInterval) * fc_nentries);
		qsort(fc_intervalsLower, fc_nentries, sizeof(SplitInterval),
			  fc_interval_cmp_lower);
		qsort(fc_intervalsUpper, fc_nentries, sizeof(SplitInterval),
			  fc_interval_cmp_upper);

		/*----
		 * 目标是形成一个左区间和一个右区间，使得每个条目区间都包含在左或右区间（或两者中）。
		 *
		 * 例如，对于区间 (0,1)、(1,3)、(2,3)、(2,4)：
		 *
		 * 0 1 2 3 4
		 * +-+
		 *	 +---+
		 *	   +-+
		 *	   +---+
		 *
		 * 左右区间的形式为 (0,a) 和 (b,4)。
		 * 我们首先考虑 b 是条目的下限的情况。
		 * 我们遍历所有条目，对于每个 b，计算最小可能的 a。然后我们考虑 a 是条目的上限的情况，对于每个 a，计算最大可能的 b。
		 *
		 * 在上述示例中，第一个循环将考虑以下分割：
		 * b=0: (0,1)-(0,4)
		 * b=1: (0,1)-(1,4)
		 * b=2: (0,3)-(2,4)
		 *
		 * 而第二个循环：
		 * a=1: (0,1)-(1,4)
		 * a=3: (0,3)-(2,4)
		 * a=4: (0,4)-(2,4)
		 */

		/*
		 * 遍历右组的下限，找到左组的最小可能上限。
		 */
		fc_i1 = 0;
		fc_i2 = 0;
		fc_rightLower = fc_intervalsLower[fc_i1].lower;
		fc_leftUpper = fc_intervalsUpper[fc_i2].lower;
		while (true)
		{
			/*
			 * 找到右组的下一个下限。
			 */
			while (fc_i1 < fc_nentries &&
				   float8_eq(fc_rightLower, fc_intervalsLower[fc_i1].lower))
			{
				if (float8_lt(fc_leftUpper, fc_intervalsLower[fc_i1].upper))
					fc_leftUpper = fc_intervalsLower[fc_i1].upper;
				fc_i1++;
			}
			if (fc_i1 >= fc_nentries)
				break;
			fc_rightLower = fc_intervalsLower[fc_i1].lower;

			/*
			 * 计算无论如何应该放置到左组的区间数。
			 */
			while (fc_i2 < fc_nentries &&
				   float8_le(fc_intervalsUpper[fc_i2].upper, fc_leftUpper))
				fc_i2++;

			/*
			 * 考虑找到的分割。
			 */
			fc_g_box_consider_split(&fc_context, fc_dim, fc_rightLower, fc_i1, fc_leftUpper, fc_i2);
		}

		/*
		 * 遍历左组的上限，找到右组的最大可能下限。
		 */
		fc_i1 = fc_nentries - 1;
		fc_i2 = fc_nentries - 1;
		fc_rightLower = fc_intervalsLower[fc_i1].upper;
		fc_leftUpper = fc_intervalsUpper[fc_i2].upper;
		while (true)
		{
			/*
			 * 查找左组的下一个上限。
			 */
			while (fc_i2 >= 0 && float8_eq(fc_leftUpper, fc_intervalsUpper[fc_i2].upper))
			{
				if (float8_gt(fc_rightLower, fc_intervalsUpper[fc_i2].lower))
					fc_rightLower = fc_intervalsUpper[fc_i2].lower;
				fc_i2--;
			}
			if (fc_i2 < 0)
				break;
			fc_leftUpper = fc_intervalsUpper[fc_i2].upper;

			/*
			 * 查找应该放置到右组的区间计数。
			 */
			while (fc_i1 >= 0 && float8_ge(fc_intervalsLower[fc_i1].lower, fc_rightLower))
				fc_i1--;

			/*
			 * 考虑找到的分割。
			 */
			fc_g_box_consider_split(&fc_context, fc_dim,
								 fc_rightLower, fc_i1 + 1, fc_leftUpper, fc_i2 + 1);
		}
	}

	/*
	 * 如果我们未能找到任何可接受的分裂，使用简单的分裂。
	 */
	if (fc_context.first)
	{
		fc_fallbackSplit(fc_entryvec, fc_v);
		PG_RETURN_POINTER(fc_v);
	}

	/*
	 * 好吧，我们现在已经选择了一个轴上的分裂。
	 *
	 * 在考虑分裂时，我们已经确定两个组中都有足够的条目以达到所需的比例，但我们并没有记住哪个条目属于哪个组。所以现在来确定这一点。
	 */

	/* 为结果分配向量 */
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nentries * sizeof(OffsetNumber));
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nentries * sizeof(OffsetNumber));
	fc_v->spl_nleft = 0;
	fc_v->spl_nright = 0;

	/* 分配左组和右组的边界框 */
	fc_leftBox = palloc0(sizeof(BOX));
	fc_rightBox = palloc0(sizeof(BOX));

	/*
	 * 为“公共条目”分配一个数组 - 可以放置到任一组而不影响所选轴上的重叠的条目。
	 */
	fc_commonEntriesCount = 0;
	fc_commonEntries = (CommonEntry *) palloc(fc_nentries * sizeof(CommonEntry));

	/* 帮助宏以将条目放入左组或右组 */
#define PLACE_LEFT(box, off)					\
	do {										\
		if (fc_v->spl_nleft > 0)					\
			fc_adjustBox(fc_leftBox, box);			\
		else									\
			*fc_leftBox = *(box);					\
		fc_v->spl_left[fc_v->spl_nleft++] = off;		\
	} while(0)

#define PLACE_RIGHT(box, off)					\
	do {										\
		if (fc_v->spl_nright > 0)					\
			fc_adjustBox(fc_rightBox, box);			\
		else									\
			*fc_rightBox = *(box);					\
		fc_v->spl_right[fc_v->spl_nright++] = off;	\
	} while(0)

	/*
	 * 分配可以明确分配的条目，并收集公共条目。
	 */
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		float8		fc_lower,
					fc_upper;

		/*
		 * 获取所选轴上的上限和下限。
		 */
		fc_box = DatumGetBoxP(fc_entryvec->vector[fc_i].key);
		if (fc_context.dim == 0)
		{
			fc_lower = fc_box->low.x;
			fc_upper = fc_box->high.x;
		}
		else
		{
			fc_lower = fc_box->low.y;
			fc_upper = fc_box->high.y;
		}

		if (float8_le(fc_upper, fc_context.leftUpper))
		{
			/* 适合左组 */
			if (float8_ge(fc_lower, fc_context.rightLower))
			{
				/* 也适合右组，因此是“公共条目” */
				fc_commonEntries[fc_commonEntriesCount++].index = fc_i;
			}
			else
			{
				/* 不适合右组，因此加入左组 */
				PLACE_LEFT(fc_box, fc_i);
			}
		}
		else
		{
			/*
			 * 每个条目应适合左组或右组。由于此条目不适合左组，因此最好适合右组。
			 */
			Assert(float8_ge(fc_lower, fc_context.rightLower));

			/* 不适合左组，因此加入右组 */
			PLACE_RIGHT(fc_box, fc_i);
		}
	}

	/*
	 * 分配“公共条目”，如果有的话。
	 */
	if (fc_commonEntriesCount > 0)
	{
		/*
		 * 计算必须放置在两个组中的条目的最小数量，以达到LIMIT_RATIO。
		 */
		int			fc_m = ceil(LIMIT_RATIO * fc_nentries);

		/*
		 * 计算连接“公共条目”到不同组的惩罚之间的差值。
		 */
		for (fc_i = 0; fc_i < fc_commonEntriesCount; fc_i++)
		{
			fc_box = DatumGetBoxP(fc_entryvec->vector[fc_commonEntries[fc_i].index].key);
			fc_commonEntries[fc_i].delta = Abs(float8_mi(fc_box_penalty(fc_leftBox, fc_box),
												   fc_box_penalty(fc_rightBox, fc_box)));
		}

		/*
		 * 按计算出的差值对“公共条目”进行排序，以优先分配最模糊的条目。
		 */
		qsort(fc_commonEntries, fc_commonEntriesCount, sizeof(CommonEntry), fc_common_entry_cmp);

		/*
		 * 在组之间分配“公共条目”。
		 */
		for (fc_i = 0; fc_i < fc_commonEntriesCount; fc_i++)
		{
			fc_box = DatumGetBoxP(fc_entryvec->vector[fc_commonEntries[fc_i].index].key);

			/*
			 * 检查我们是否必须将此条目放置到任一组中，以达到LIMIT_RATIO。
			 */
			if (fc_v->spl_nleft + (fc_commonEntriesCount - fc_i) <= fc_m)
				PLACE_LEFT(fc_box, fc_commonEntries[fc_i].index);
			else if (fc_v->spl_nright + (fc_commonEntriesCount - fc_i) <= fc_m)
				PLACE_RIGHT(fc_box, fc_commonEntries[fc_i].index);
			else
			{
				/* 否则选择惩罚最小的组 */
				if (fc_box_penalty(fc_leftBox, fc_box) < fc_box_penalty(fc_rightBox, fc_box))
					PLACE_LEFT(fc_box, fc_commonEntries[fc_i].index);
				else
					PLACE_RIGHT(fc_box, fc_commonEntries[fc_i].index);
			}
		}
	}

	fc_v->spl_ldatum = PointerGetDatum(fc_leftBox);
	fc_v->spl_rdatum = PointerGetDatum(fc_rightBox);
	PG_RETURN_POINTER(fc_v);
}

/*
 * 等价方法
 *
 * 适用于框、点、圆和多边形，所有这些都将框作为GiST索引条目存储。
 *
 * 仅当框完全相同时返回true。我们不能在这里使用模糊比较，否则会破坏索引一致性；因此，这与box_same()不等效。
 */
Datum gist_box_same(PG_FUNCTION_ARGS)
{
	BOX		   *fc_b1 = PG_GETARG_BOX_P(0);
	BOX		   *fc_b2 = PG_GETARG_BOX_P(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);

	if (fc_b1 && fc_b2)
		*fc_result = (float8_eq(fc_b1->low.x, fc_b2->low.x) &&
				   float8_eq(fc_b1->low.y, fc_b2->low.y) &&
				   float8_eq(fc_b1->high.x, fc_b2->high.x) &&
				   float8_eq(fc_b1->high.y, fc_b2->high.y));
	else
		*fc_result = (fc_b1 == NULL && fc_b2 == NULL);
	PG_RETURN_POINTER(fc_result);
}

/*
 * 框的叶级一致性：仅应用查询操作符
 */
static bool fc_gist_box_leaf_consistent(BOX *fc_key, BOX *fc_query, StrategyNumber fc_strategy)
{
	bool		fc_retval;

	switch (fc_strategy)
	{
		case RTLeftStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_left,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTOverLeftStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_overleft,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTOverlapStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_overlap,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTOverRightStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_overright,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTRightStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_right,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTSameStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_same,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTContainsStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_contain,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTContainedByStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_contained,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTOverBelowStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_overbelow,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTBelowStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_below,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTAboveStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_above,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTOverAboveStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_overabove,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			fc_retval = false;		/* 保持编译器安静 */
			break;
	}
	return fc_retval;
}

/*****************************************
 * 共同的rtree函数（用于框、多边形和圆）
 *****************************************/

/*
 * 所有这些类型的内部页面一致性
 *
 * 我们可以使用相同的功能，因为所有类型都使用边界框作为内部页面表示。
 */
static bool fc_rtree_internal_consistent(BOX *fc_key, BOX *fc_query, StrategyNumber fc_strategy)
{
	bool		fc_retval;

	switch (fc_strategy)
	{
		case RTLeftStrategyNumber:
			fc_retval = !DatumGetBool(DirectFunctionCall2(box_overright,
													   PointerGetDatum(fc_key),
													   PointerGetDatum(fc_query)));
			break;
		case RTOverLeftStrategyNumber:
			fc_retval = !DatumGetBool(DirectFunctionCall2(box_right,
													   PointerGetDatum(fc_key),
													   PointerGetDatum(fc_query)));
			break;
		case RTOverlapStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_overlap,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTOverRightStrategyNumber:
			fc_retval = !DatumGetBool(DirectFunctionCall2(box_left,
													   PointerGetDatum(fc_key),
													   PointerGetDatum(fc_query)));
			break;
		case RTRightStrategyNumber:
			fc_retval = !DatumGetBool(DirectFunctionCall2(box_overleft,
													   PointerGetDatum(fc_key),
													   PointerGetDatum(fc_query)));
			break;
		case RTSameStrategyNumber:
		case RTContainsStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_contain,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTContainedByStrategyNumber:
			fc_retval = DatumGetBool(DirectFunctionCall2(box_overlap,
													  PointerGetDatum(fc_key),
													  PointerGetDatum(fc_query)));
			break;
		case RTOverBelowStrategyNumber:
			fc_retval = !DatumGetBool(DirectFunctionCall2(box_above,
													   PointerGetDatum(fc_key),
													   PointerGetDatum(fc_query)));
			break;
		case RTBelowStrategyNumber:
			fc_retval = !DatumGetBool(DirectFunctionCall2(box_overabove,
													   PointerGetDatum(fc_key),
													   PointerGetDatum(fc_query)));
			break;
		case RTAboveStrategyNumber:
			fc_retval = !DatumGetBool(DirectFunctionCall2(box_overbelow,
													   PointerGetDatum(fc_key),
													   PointerGetDatum(fc_query)));
			break;
		case RTOverAboveStrategyNumber:
			fc_retval = !DatumGetBool(DirectFunctionCall2(box_below,
													   PointerGetDatum(fc_key),
													   PointerGetDatum(fc_query)));
			break;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			fc_retval = false;		/* 保持编译器安静 */
			break;
	}
	return fc_retval;
}

/**************************************************
 * 多边形操作
 **************************************************/

/*
 * GiST 对多边形进行压缩：通过其边界框表示多边形
 */
Datum gist_poly_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_retval;

	if (fc_entry->leafkey)
	{
		POLYGON    *fc_in = DatumGetPolygonP(fc_entry->key);
		BOX		   *fc_r;

		fc_r = (BOX *) palloc(sizeof(BOX));
		memcpy((void *) fc_r, (void *) &(fc_in->boundbox), sizeof(BOX));

		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_r),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
	}
	else
		fc_retval = fc_entry;
	PG_RETURN_POINTER(fc_retval);
}

/*
 * 多边形的 GiST 一致性方法
 */
Datum gist_poly_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	POLYGON    *fc_query = PG_GETARG_POLYGON_P(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	bool		fc_result;

	/* 此函数处理的所有情况都是不准确的 */
	*fc_recheck = true;

	if (DatumGetBoxP(fc_entry->key) == NULL || fc_query == NULL)
		PG_RETURN_BOOL(false);

	/*
	 * 由于操作符无论如何都需要重新检查，我们可以在叶节点
	 * 仅使用 rtree_internal_consistent。 （这部分有效
	 * 是因为索引条目是边界框而不是多边形。）
	 */
	fc_result = fc_rtree_internal_consistent(DatumGetBoxP(fc_entry->key),
									   &(fc_query->boundbox), fc_strategy);

	/* 避免如果提供的多边形被烘烤而导致内存泄漏 */
	PG_FREE_IF_COPY(fc_query, 1);

	PG_RETURN_BOOL(fc_result);
}

/**************************************************
 * 圆形操作
 **************************************************/

/*
 * GiST 对圆形进行压缩：通过其边界框表示圆形
 */
Datum gist_circle_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_retval;

	if (fc_entry->leafkey)
	{
		CIRCLE	   *fc_in = DatumGetCircleP(fc_entry->key);
		BOX		   *fc_r;

		fc_r = (BOX *) palloc(sizeof(BOX));
		fc_r->high.x = float8_pl(fc_in->center.x, fc_in->radius);
		fc_r->low.x = float8_mi(fc_in->center.x, fc_in->radius);
		fc_r->high.y = float8_pl(fc_in->center.y, fc_in->radius);
		fc_r->low.y = float8_mi(fc_in->center.y, fc_in->radius);

		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_r),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
	}
	else
		fc_retval = fc_entry;
	PG_RETURN_POINTER(fc_retval);
}

/*
 * 圆形的 GiST 一致性方法
 */
Datum gist_circle_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	CIRCLE	   *fc_query = PG_GETARG_CIRCLE_P(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	BOX			fc_bbox;
	bool		fc_result;

	/* 此函数处理的所有情况都是不准确的 */
	*fc_recheck = true;

	if (DatumGetBoxP(fc_entry->key) == NULL || fc_query == NULL)
		PG_RETURN_BOOL(false);

	/*
	 * 由于操作符无论如何都需要重新检查，我们可以在叶节点
	 * 仅使用 rtree_internal_consistent。 （这部分有效
	 * 是因为索引条目是边界框而不是圆形。）
	 */
	fc_bbox.high.x = float8_pl(fc_query->center.x, fc_query->radius);
	fc_bbox.low.x = float8_mi(fc_query->center.x, fc_query->radius);
	fc_bbox.high.y = float8_pl(fc_query->center.y, fc_query->radius);
	fc_bbox.low.y = float8_mi(fc_query->center.y, fc_query->radius);

	fc_result = fc_rtree_internal_consistent(DatumGetBoxP(fc_entry->key),
									   &fc_bbox, fc_strategy);

	PG_RETURN_BOOL(fc_result);
}

/**************************************************
 * 点操作
 **************************************************/

Datum gist_point_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);

	if (fc_entry->leafkey)			/* 实际上是点 */
	{
		BOX		   *fc_box = palloc(sizeof(BOX));
		Point	   *fc_point = DatumGetPointP(fc_entry->key);
		GISTENTRY  *fc_retval = palloc(sizeof(GISTENTRY));

		fc_box->high = fc_box->low = *fc_point;

		gistentryinit(*fc_retval, BoxPGetDatum(fc_box),
					  fc_entry->rel, fc_entry->page, fc_entry->offset, false);

		PG_RETURN_POINTER(fc_retval);
	}

	PG_RETURN_POINTER(fc_entry);
}

/*
 * 点的 GiST 获取方法
 *
 * 从其边界框坐标获取点坐标并形成新的
 * gistentry。
 */
Datum gist_point_fetch(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	BOX		   *fc_in = DatumGetBoxP(fc_entry->key);
	Point	   *fc_r;
	GISTENTRY  *fc_retval;

	fc_retval = palloc(sizeof(GISTENTRY));

	fc_r = (Point *) palloc(sizeof(Point));
	fc_r->x = fc_in->high.x;
	fc_r->y = fc_in->high.y;
	gistentryinit(*fc_retval, PointerGetDatum(fc_r),
				  fc_entry->rel, fc_entry->page,
				  fc_entry->offset, false);

	PG_RETURN_POINTER(fc_retval);
}


#define point_point_distance(p1,p2) \
	DatumGetFloat8(DirectFunctionCall2(point_distance, \
									   PointPGetDatum(p1), PointPGetDatum(p2)))

static float8 fc_computeDistance(bool fc_isLeaf, BOX *fc_box, Point *fc_point)
{
	float8		fc_result = 0.0;

	if (fc_isLeaf)
	{
		/* 简单的点到点距离 */
		fc_result = point_point_distance(fc_point, &fc_box->low);
	}
	else if (fc_point->x <= fc_box->high.x && fc_point->x >= fc_box->low.x &&
			 fc_point->y <= fc_box->high.y && fc_point->y >= fc_box->low.y)
	{
		/* 点在框内 */
		fc_result = 0.0;
	}
	else if (fc_point->x <= fc_box->high.x && fc_point->x >= fc_box->low.x)
	{
		/* 点在框的上方或下方 */
		Assert(fc_box->low.y <= fc_box->high.y);
		if (fc_point->y > fc_box->high.y)
			fc_result = float8_mi(fc_point->y, fc_box->high.y);
		else if (fc_point->y < fc_box->low.y)
			fc_result = float8_mi(fc_box->low.y, fc_point->y);
		else
			elog(ERROR, "inconsistent point values");
	}
	else if (fc_point->y <= fc_box->high.y && fc_point->y >= fc_box->low.y)
	{
		/* 点在框的左侧或右侧 */
		Assert(fc_box->low.x <= fc_box->high.x);
		if (fc_point->x > fc_box->high.x)
			fc_result = float8_mi(fc_point->x, fc_box->high.x);
		else if (fc_point->x < fc_box->low.x)
			fc_result = float8_mi(fc_box->low.x, fc_point->x);
		else
			elog(ERROR, "inconsistent point values");
	}
	else
	{
		/* 最近的点将是一个顶点 */
		Point		fc_p;
		float8		fc_subresult;

		fc_result = point_point_distance(fc_point, &fc_box->low);

		fc_subresult = point_point_distance(fc_point, &fc_box->high);
		if (fc_result > fc_subresult)
			fc_result = fc_subresult;

		fc_p.x = fc_box->low.x;
		fc_p.y = fc_box->high.y;
		fc_subresult = point_point_distance(fc_point, &fc_p);
		if (fc_result > fc_subresult)
			fc_result = fc_subresult;

		fc_p.x = fc_box->high.x;
		fc_p.y = fc_box->low.y;
		fc_subresult = point_point_distance(fc_point, &fc_p);
		if (fc_result > fc_subresult)
			fc_result = fc_subresult;
	}

	return fc_result;
}

static bool fc_gist_point_consistent_internal(StrategyNumber fc_strategy,
							   bool fc_isLeaf, BOX *fc_key, Point *fc_query)
{
	bool		fc_result = false;

	switch (fc_strategy)
	{
		case RTLeftStrategyNumber:
			fc_result = FPlt(fc_key->low.x, fc_query->x);
			break;
		case RTRightStrategyNumber:
			fc_result = FPgt(fc_key->high.x, fc_query->x);
			break;
		case RTAboveStrategyNumber:
			fc_result = FPgt(fc_key->high.y, fc_query->y);
			break;
		case RTBelowStrategyNumber:
			fc_result = FPlt(fc_key->low.y, fc_query->y);
			break;
		case RTSameStrategyNumber:
			if (fc_isLeaf)
			{
				/* key.high 必须等于 key.low，因此我们可以忽略它 */
				fc_result = (FPeq(fc_key->low.x, fc_query->x) &&
						  FPeq(fc_key->low.y, fc_query->y));
			}
			else
			{
				fc_result = (FPle(fc_query->x, fc_key->high.x) &&
						  FPge(fc_query->x, fc_key->low.x) &&
						  FPle(fc_query->y, fc_key->high.y) &&
						  FPge(fc_query->y, fc_key->low.y));
			}
			break;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			fc_result = false;		/* 保持编译器安静 */
			break;
	}

	return fc_result;
}

#define GeoStrategyNumberOffset		20
#define PointStrategyNumberGroup	0
#define BoxStrategyNumberGroup		1
#define PolygonStrategyNumberGroup	2
#define CircleStrategyNumberGroup	3

Datum gist_point_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	bool		fc_result;
	StrategyNumber fc_strategyGroup;

	/*
	 * 我们必须重新映射这些策略编号，以使这种难看的
	 * 分类逻辑能够正常工作。
	 */
	if (fc_strategy == RTOldBelowStrategyNumber)
		fc_strategy = RTBelowStrategyNumber;
	else if (fc_strategy == RTOldAboveStrategyNumber)
		fc_strategy = RTAboveStrategyNumber;

	fc_strategyGroup = fc_strategy / GeoStrategyNumberOffset;
	switch (fc_strategyGroup)
	{
		case PointStrategyNumberGroup:
			fc_result = fc_gist_point_consistent_internal(fc_strategy % GeoStrategyNumberOffset,
													GIST_LEAF(fc_entry),
													DatumGetBoxP(fc_entry->key),
													PG_GETARG_POINT_P(1));
			*fc_recheck = false;
			break;
		case BoxStrategyNumberGroup:
			{
				/*
				 * 该组中唯一的操作符是 point <@ box (on_pb)，所以
				 * 我们不需要再次检查策略。
				 *
				 * 出于历史原因，on_pb 使用精确而非模糊
				 * 比较。 我们可以在内部页面使用 box_overlap，
				 * 但这可能导致无意义地访问子页面，
				 * 因为 box_overlap 使用模糊比较。
				 * 相反，我们编写一个非模糊重叠测试。 这段代码
				 * 也将用于叶页面测试，因为叶键具有
				 * high == low。
				 */
				BOX		   *fc_query,
						   *fc_key;

				fc_query = PG_GETARG_BOX_P(1);
				fc_key = DatumGetBoxP(fc_entry->key);

				fc_result = (fc_key->high.x >= fc_query->low.x &&
						  fc_key->low.x <= fc_query->high.x &&
						  fc_key->high.y >= fc_query->low.y &&
						  fc_key->low.y <= fc_query->high.y);
				*fc_recheck = false;
			}
			break;
		case PolygonStrategyNumberGroup:
			{
				POLYGON    *fc_query = PG_GETARG_POLYGON_P(1);

				fc_result = DatumGetBool(DirectFunctionCall5(gist_poly_consistent,
														  PointerGetDatum(fc_entry),
														  PolygonPGetDatum(fc_query),
														  Int16GetDatum(RTOverlapStrategyNumber),
														  0, PointerGetDatum(fc_recheck)));

				if (GIST_LEAF(fc_entry) && fc_result)
				{
					/*
					 * 我们在叶页面上，快速检查显示多边形的
					 * 边界框和点有重叠
					 */
					BOX		   *fc_box = DatumGetBoxP(fc_entry->key);

					Assert(fc_box->high.x == fc_box->low.x
						   && fc_box->high.y == fc_box->low.y);
					fc_result = DatumGetBool(DirectFunctionCall2(poly_contain_pt,
															  PolygonPGetDatum(fc_query),
															  PointPGetDatum(&fc_box->high)));
					*fc_recheck = false;
				}
			}
			break;
		case CircleStrategyNumberGroup:
			{
				CIRCLE	   *fc_query = PG_GETARG_CIRCLE_P(1);

				fc_result = DatumGetBool(DirectFunctionCall5(gist_circle_consistent,
														  PointerGetDatum(fc_entry),
														  CirclePGetDatum(fc_query),
														  Int16GetDatum(RTOverlapStrategyNumber),
														  0, PointerGetDatum(fc_recheck)));

				if (GIST_LEAF(fc_entry) && fc_result)
				{
					/*
					 * 我们在叶页面上，快速检查显示多边形的
					 * 边界框和点有重叠
					 */
					BOX		   *fc_box = DatumGetBoxP(fc_entry->key);

					Assert(fc_box->high.x == fc_box->low.x
						   && fc_box->high.y == fc_box->low.y);
					fc_result = DatumGetBool(DirectFunctionCall2(circle_contain_pt,
															  CirclePGetDatum(fc_query),
															  PointPGetDatum(&fc_box->high)));
					*fc_recheck = false;
				}
			}
			break;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			fc_result = false;		/* 保持编译器安静 */
			break;
	}

	PG_RETURN_BOOL(fc_result);
}

Datum gist_point_distance(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);
	float8		fc_distance;
	StrategyNumber fc_strategyGroup = fc_strategy / GeoStrategyNumberOffset;

	switch (fc_strategyGroup)
	{
		case PointStrategyNumberGroup:
			fc_distance = fc_computeDistance(GIST_LEAF(fc_entry),
									   DatumGetBoxP(fc_entry->key),
									   PG_GETARG_POINT_P(1));
			break;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			fc_distance = 0.0;		/* 保持编译器安静 */
			break;
	}

	PG_RETURN_FLOAT8(fc_distance);
}

static float8 fc_gist_bbox_distance(GISTENTRY *fc_entry, Datum fc_query, StrategyNumber fc_strategy)
{
	float8		fc_distance;
	StrategyNumber fc_strategyGroup = fc_strategy / GeoStrategyNumberOffset;

	switch (fc_strategyGroup)
	{
		case PointStrategyNumberGroup:
			fc_distance = fc_computeDistance(false,
									   DatumGetBoxP(fc_entry->key),
									   DatumGetPointP(fc_query));
			break;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			fc_distance = 0.0;		/* 保持编译器安静 */
	}

	return fc_distance;
}

Datum gist_box_distance(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	Datum		fc_query = PG_GETARG_DATUM(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid subtype = PG_GETARG_OID(3); */
	/* bool	   *recheck = (bool *) PG_GETARG_POINTER(4); */
	float8		fc_distance;

	fc_distance = fc_gist_bbox_distance(fc_entry, fc_query, fc_strategy);

	PG_RETURN_FLOAT8(fc_distance);
}

/*
 * 不精确的 GiST 距离方法，用于存储边界框的几何类型。
 *
 * 计算从点到索引条目的损失距离。结果是不精确的，因为索引条目是边界框，而不是被索引几何类型的精确形状。我们使用从点到索引条目 MBR 的距离。这是从点到被索引几何类型距离的下限估计。
 */
Datum gist_circle_distance(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	Datum		fc_query = PG_GETARG_DATUM(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	float8		fc_distance;

	fc_distance = fc_gist_bbox_distance(fc_entry, fc_query, fc_strategy);
	*fc_recheck = true;

	PG_RETURN_FLOAT8(fc_distance);
}

Datum gist_poly_distance(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	Datum		fc_query = PG_GETARG_DATUM(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	float8		fc_distance;

	fc_distance = fc_gist_bbox_distance(fc_entry, fc_query, fc_strategy);
	*fc_recheck = true;

	PG_RETURN_FLOAT8(fc_distance);
}

/*
 * 用于快速索引构建的 Z-order 函数
 */

/*
 * 计算一个点的 Z 值
 *
 * Z-order（也称为 Morton 码）将二维点映射到单个整数，方式上保留了局部性。在二维空间中相近的点被映射到不远的整数。我们通过交错 X 和 Y 分量的位来实现这一点。
 *
 * Morton 码通常仅为整数定义，但点的 X 和 Y 值是浮点数。我们期望浮点数为 IEEE 格式。
 */
static uint64 fc_point_zorder_internal(float4 fc_x, float4 fc_y)
{
	uint32		fc_ix = fc_ieee_float32_to_uint32(fc_x);
	uint32		fc_iy = fc_ieee_float32_to_uint32(fc_y);

	/* 交错位 */
	return fc_part_bits32_by2(fc_ix) | (fc_part_bits32_by2(fc_iy) << 1);
}

/* 使用零交错 32 位 */
static uint64 fc_part_bits32_by2(uint32 fc_x)
{
	uint64		fc_n = fc_x;

	fc_n = (fc_n | (fc_n << 16)) & UINT64CONST(0x0000FFFF0000FFFF);
	fc_n = (fc_n | (fc_n << 8)) & UINT64CONST(0x00FF00FF00FF00FF);
	fc_n = (fc_n | (fc_n << 4)) & UINT64CONST(0x0F0F0F0F0F0F0F0F);
	fc_n = (fc_n | (fc_n << 2)) & UINT64CONST(0x3333333333333333);
	fc_n = (fc_n | (fc_n << 1)) & UINT64CONST(0x5555555555555555);

	return fc_n;
}

/*
 * 将 32 位 IEEE 浮点数转换为 uint32，以保持顺序
 */
static uint32 fc_ieee_float32_to_uint32(float fc_f)
{
	/*----
	 *
	 * IEEE 754 浮点格式
	 * ------------------------------
	 *
	 * IEEE 754 浮点数采用以下格式：
	 *
	 *   指数 (8 位)
	 *   |
	 * s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm
	 * |          |
	 * 符号       尾数 (23 位)
	 *
	 * 无穷大是指数中所有位均设置且尾数全为零。负无穷大也是如此，但符号位设置为 1。
	 *
	 * NaN 由指数中所有位均设置以及尾数中最低有效位也设置来表示。尾数的其余位可用于区分不同类型的 NaN。
	 *
	 * IEEE 格式具有良好的性质，即当你获取位表示并将其解释为整数时，顺序得以保持，除了符号之外。对于正负无穷大值也是如此。
	 *
	 * 映射到 uint32
	 * -----------------
	 *
	 * 为了平滑过渡从负值到正值，我们将浮点数映射到无符号整数，如下所示：
	 *
	 * x < 0 映射到范围 0-7FFFFFFF
	 * x = 0 映射到值 8000000（正零和负零）
	 * x > 0 映射到范围 8000001-FFFFFFFF
	 *
	 * 我们不关心区分不同类型的 NaN，因此它们都映射到相同的任意值 FFFFFFFF。由于 NaN 的 IEEE 位表示，没有其他非 NaN 值会映射到 FFFFFFFF。实际上，在 uint32 空间的两端有一系列未使用的值。
	 */
	if (isnan(fc_f))
		return 0xFFFFFFFF;
	else
	{
		union
		{
			float		f;
			uint32		i;
		}			fc_u;

		fc_u.f = fc_f;

		/* 检查符号位 */
		if ((fc_u.i & 0x80000000) != 0)
		{
			/*
			 * 将负值映射到范围 0-7FFFFFFF。该指令同时将符号位翻转为 0。
			 */
			Assert(fc_f <= 0);		/* 可以是 -0 */
			fc_u.i ^= 0xFFFFFFFF;
		}
		else
		{
			/* 将正值（或 0）映射到范围 80000000-FFFFFFFF */
			fc_u.i |= 0x80000000;
		}

		return fc_u.i;
	}
}

/*
 * 比较点的 Z-order
 */
static int fc_gist_bbox_zorder_cmp(Datum fc_a, Datum fc_b, SortSupport fc_ssup)
{
	Point	   *fc_p1 = &(DatumGetBoxP(fc_a)->low);
	Point	   *fc_p2 = &(DatumGetBoxP(fc_b)->low);
	uint64		fc_z1;
	uint64		fc_z2;

	/*
	 * 首先进行快速的相等性检查。一般来说，这是否值得还不清楚，
	 * 但当用作带有缩写键的平局打破者时，肯定是值得的，
	 */
	if (fc_p1->x == fc_p2->x && fc_p1->y == fc_p2->y)
		return 0;

	fc_z1 = fc_point_zorder_internal(fc_p1->x, fc_p1->y);
	fc_z2 = fc_point_zorder_internal(fc_p2->x, fc_p2->y);
	if (fc_z1 > fc_z2)
		return 1;
	else if (fc_z1 < fc_z2)
		return -1;
	else
		return 0;
}

/*
 * Z-order 比较的缩写版本
 *
 * 缩写格式是从两个 32 位浮点数计算得出的 Z-order 值。如果 SIZEOF_DATUM == 8，则 64 位 Z-order 值完全适合缩写 Datum，否则使用其最高有效位。
 */
static Datum fc_gist_bbox_zorder_abbrev_convert(Datum fc_original, SortSupport fc_ssup)
{
	Point	   *fc_p = &(DatumGetBoxP(fc_original)->low);
	uint64		fc_z;

	fc_z = fc_point_zorder_internal(fc_p->x, fc_p->y);

#if SIZEOF_DATUM == 8
	return (Datum) fc_z;
#else
	return (Datum) (z >> 32);
#endif
}

/*
 * 我们从不考虑中止缩写。
 *
 * 在 64 位系统上，缩写不是有损的，因此始终是值得的。（也许在 32 位系统上不是，但我们不费心去判断。）
 */
static bool fc_gist_bbox_zorder_abbrev_abort(int fc_memtupcount, SortSupport fc_ssup)
{
	return false;
}

/*
 * 用于快速 GiST 索引构建的排序支持例程。
 */
Datum gist_point_sortsupport(PG_FUNCTION_ARGS)
{
	SortSupport fc_ssup = (SortSupport) PG_GETARG_POINTER(0);

	if (fc_ssup->abbreviate)
	{
		fc_ssup->comparator = ssup_datum_unsigned_cmp;
		fc_ssup->abbrev_converter = fc_gist_bbox_zorder_abbrev_convert;
		fc_ssup->abbrev_abort = fc_gist_bbox_zorder_abbrev_abort;
		fc_ssup->abbrev_full_comparator = fc_gist_bbox_zorder_cmp;
	}
	else
	{
		fc_ssup->comparator = fc_gist_bbox_zorder_cmp;
	}
	PG_RETURN_VOID();
}
